package com.it.data_tree.tree.binaryTree;

import com.it.data_tree.util.ColorPrintln;

import java.util.LinkedList;

/**
 * 树节点类
 */
public class TreeNode {
    public static void main(String[] args) {

    }

    /**
     * 前序遍历 (使用递归)
     *
     * @param node
     */
    public static void preTreeNode(Node node) {
        if (node == null) {
            return;
        }
        ColorPrintln.redPrintln(node.getNo());
        preTreeNode(node.getLeft());
        preTreeNode(node.getRight());

    }

    /**
     * 中序遍历 (使用递归)
     * @param node
     */
    public static void inxTreeNode(Node node) {
        if (node == null) {
            return;
        }
        inxTreeNode(node.getLeft());
        ColorPrintln.bluePrintln(node.getNo());
        inxTreeNode(node.getRight());

    }

    /**
     * 后续遍历 (使用递归)
     * @param node
     */
    public static void postTreeNode(Node node) {
        if (node == null) {
            return;
        }
        postTreeNode(node.getLeft());
        postTreeNode(node.getRight());
        ColorPrintln.greenPrintln(node.getNo());

    }

    /**
     * 前序遍历（不使用递归）
     * @param node
     */
    public static void preTreeByNoRecursion(Node node){
        Node curr = node; // 代表当前节点
        LinkedList<Node> list = new LinkedList<>();
        while (curr != null || !list.isEmpty()) {
            if (curr != null) {
                ColorPrintln.redPrintln("去===>" + curr.getNo());
                list.push(curr);
                curr = curr.getLeft();
            }else {
                Node node1 = list.pop();
//                ColorPrintln.cyanPrintln("回===>" + node1.getNo());
                curr = node1.getRight();
            }
        }
    }

    /**
     * 中序遍历（不使用递归）
     * @param node
     */
    public static void inxTreeByNoRecursion(Node node){
        Node curr = node; // 代表当前节点
        LinkedList<Node> list = new LinkedList<>();
        while (curr != null || !list.isEmpty()) {
            if (curr != null) {
//                ColorPrintln.redPrintln("去===>" + curr.getNo());
                list.push(curr);
                curr = curr.getLeft();
            }else {
                Node node1 = list.pop();
                ColorPrintln.cyanPrintln("回===>" + node1.getNo());
                curr = node1.getRight();
            }
        }
    }

    /**
     * 后序遍历（不使用递归）
     * @param node
     */
    public static void postTreeByNoRecursion(Node node){
        Node curr = node; // 代表当前节点
        LinkedList<Node> list = new LinkedList<>();
        Node pop = null;
        while (curr != null || !list.isEmpty()) {
            if (curr != null) {
//                ColorPrintln.redPrintln("去===>" + curr.getNo());
                list.push(curr);
                curr = curr.getLeft();
            }else {
                Node peek = list.peek();
                if (peek.getRight() == null || peek.getRight() == pop){
                    pop = list.pop();
                    ColorPrintln.cyanPrintln("回===>" + pop.getNo());
                }else {
                    curr = peek.getRight();
                }


            }
        }
    }

    /**
     * 前中后序遍历（不使用递归）
     * @param node
     */
    public static void allTreeByNoRecursion(Node node){
        Node curr = node; // 代表当前节点
        LinkedList<Node> list = new LinkedList<>();
        Node pop = null;
        while (curr != null || !list.isEmpty()) {

            if (curr != null) {
                list.push(curr);
                ColorPrintln.greenPrintln("前序遍历 ====> " + curr.getNo());
                // 待处理左子树
                curr = curr.getLeft();
            }else {
                Node peek = list.peek();
                // 没有右子树
                if (peek.getRight() == null){
                    ColorPrintln.yellowPrintln("中序遍历 ====> " + peek.getNo());
                    pop = list.pop();
                    ColorPrintln.redPrintln("后序遍历 ====> " + pop.getNo());
                // 右子树处理完成
                }else if (peek.getRight() == pop){
                    pop = list.pop();
                    ColorPrintln.redPrintln("后序遍历 ====> " + pop.getNo());
                // 待处理右子树
                }else {
                    ColorPrintln.yellowPrintln("中序遍历 ====> " + peek.getNo());
                    curr = peek.getRight();
                }
            }
        }
    }

}
